0XFF 珂朵莉美图欣赏
行了别看了赶紧进入正题
0X00 简介
设计一个数据结构，区间加？
简单，线段树！
求区间第k小值？
主席树板子题！
区间推平赋值？还要查询区间k次幂的和？
……
不知道怎么办了吧！这四个操作是珂朵莉树最经典的操作。下面让我们跟着题目往下看。
0X01 模板题 - 基本操作
总结一下上面说的操作：区间加、区间赋值、查询区间第k小、查询区间幂次和。
下面看一道模板题：传送门
不要一看是黑题就害怕，珂朵莉树的本质其实就是拿一个set瞎暴力！
0X01-1 结构体定义
typedef long long ll;
struct Node
{
ll l, r;
mutable ll v;
Node(ll x, ll y=-1, ll z=0) : l(x), r(y), v(z) {}
bool operator < (const Node &a) const {return l < a.l;}
}
set<Node> ODT;
typedef set<Node>::iterator IT;
l、r表示区间左右端点，v是区间权值。下面那行定义了一个构造函数，方便以后使用。最后重载了小于运算符，按照区间左端点顺序排序，因为后面用的时候区间不存在重叠，所以其实就是让区间依次排序。
0X01-2 split
split操作用于将整段在pos的位置拆分为两小段，方便后续操作。
IT split(ll pos)
{
IT iter = ODT.lower_bound(Node(pos));
if(iter != ODT.end() && iter->l == pos) return iter;//不需要拆分
--iter;//一定在前一区间内
ll L = iter->l, R = iter->r, V = iter->v;//把值取出
ODT.erase(iter);//删除待拆分的原区间
ODT.insert(Node(L, pos-1, V));//插入新区间，Node(L, pos-1, V)利用构造函数生成Node类
return ODT.insert(Node(pos, R, V)).first;//插入新区间并返回目标位置
}
0X01-3 区间加
区间加法其实就是把要加的段取出来暴力加。注意这里必须先split右边再split左边！
void update(ll l, ll r, ll dt)
{
IT iterR = split(r+1), iterL = split(l);//必须先split右边再split左边
for(iterL;iterL!=iterR;++iterL) iterL->v += dt;//暴力加整个区间
}
0X01-4 区间赋值
区间赋值也是取出要用的区间，把所有范围内的区间删掉，然后重新插入一个新区间。
void assign_val(ll l, ll r, ll w)
{
IT iterR = split(r+1), iterL = split(l);
ODT.erase(iterL, iterR);//删除赋值范围内所有区间
ODT.insert(Node(l, r, w));//添加被删除的区间，权值直接改成要赋的值
}
0X01-5 求区间内排名为k的数
就是求区间第k小，把区间所有数压进vector，然后排序即可。
ll ranking(ll l, ll r, ll k)
{
vector<pair<ll, ll> > v;//声明vector，pair->first是值，pair->second是个数
IT iterR = split(r+1), iterL = split(l);
for(iterL;iterL!=iterR;++iterL) v.push_back(make_pair(iterL->v, iterL->r-iterL->l+1));//把区间内所有数push进vector
sort(v.begin(), v.end());//vector排序
for(vector<pair<ll, ll> >::iterator iter=v.begin();iter!=v.end();++iter)
{
k -= iter->second;
if(k <= 0) return iter->first;//不断降低k，直到k<=0，输出
}
}
0X01-6 求区间所有数乘k次幂的和
区间幂次和，暴力算出所有的幂次和，加起来即可，这里需要使用快速幂。
ll qpow(ll x, ll y, ll MOD)//快速幂，相信你们都会，不用解释了
{
ll ret = 1;
ll ans = x % MOD;
while(y)
{
if(y&1) ret = ret * ans % MOD;
ans = ans * ans % MOD;
y >>= 1;
}
return ret;
}
ll sum(ll l, ll r, ll x, ll y)//区间幂次和
{
ll ans = 0;
IT iterR = split(r+1), iterL = split(l);
for(iterL;iterL!=iterR;++iterL)//枚举所有区间，算出幂次和
ans = (ans + (iterL->r - iterL->l + 1) * qpow(iterL->v, x, y)) % y;
return ans;
}
0X01-7 完整程序
下面就是完整程序了。怎么样？是不是感觉很暴力很容易理解？
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1000000007LL;
const ll MAXN = 100001;
ll n, m, seed, vmax;
ll a[MAXN];
struct Node
{
ll l, r;
mutable ll v;
Node(ll x, ll y = -1, ll z = 0): l(x), r(y), v(z) {}
bool operator < (const Node &a) const {return l < a.l;}
};
typedef set<Node>::iterator IT;
set<Node> ODT;
ll rnd() //题目中要求的随机函数
{
ll ret = seed;
seed = (seed * 7 + 13) % mod;
return ret;
}
IT split(ll pos)
{
IT iter = ODT.lower_bound(Node(pos));
if(iter != ODT.end() && iter->l == pos) return iter;
--iter;
ll L = iter->l, R = iter->r, V = iter->v;
ODT.erase(iter);
ODT.insert(Node(L, pos-1, V));
return ODT.insert(Node(pos, R, V)).first;
}
void update(ll l, ll r, ll dt)
{
IT iterR = split(r+1), iterL = split(l);
for(iterL;iterL!=iterR;++iterL) iterL->v += dt;
}
void assign_val(ll l, ll r, ll w)
{
IT iterR = split(r+1), iterL = split(l);
ODT.erase(iterL, iterR);
ODT.insert(Node(l, r, w));
}
ll ranking(ll l, ll r, ll k)
{
vector<pair<ll, ll> > v;
IT iterR = split(r+1), iterL = split(l);
for(iterL;iterL!=iterR;++iterL) v.push_back(make_pair(iterL->v, iterL->r-iterL->l+1));
sort(v.begin(), v.end());
for(vector<pair<ll, ll> >::iterator iter=v.begin();iter!=v.end();++iter)
{
k -= iter->second;
if(k <= 0) return iter->first;
}
}
ll qpow(ll x, ll y, ll MOD)
{
ll ret = 1;
ll ans = x % MOD;
while(y)
{
if(y&1) ret = ret * ans % MOD;
ans = ans * ans % MOD;
y >>= 1;
}
return ret;
}
ll sum(ll l, ll r, ll x, ll y)
{
ll ans = 0;
IT iterR = split(r+1), iterL = split(l);
for(iterL;iterL!=iterR;++iterL)
ans = (ans + (iterL->r - iterL->l + 1) * qpow(iterL->v, x, y)) % y;
return ans;
}
int main()
{
scanf("%lld%lld%lld%lld", &n, &m, &seed, &vmax);
for(ll i=1;i<=n;i++)
{
a[i] = (rnd() % vmax) + 1;
ODT.insert(Node(i, i, a[i]));
}
for(ll i=1;i<=m;i++)
{
ll op = rnd() % 4 + 1;
ll l = rnd() % n + 1;
ll r = rnd() % n + 1;
if(l > r) swap(l, r);
ll x, y;
if(op == 3) x = rnd() % (r - l + 1) + 1;
else x = rnd() % vmax + 1;
if(op == 4) y = rnd() % vmax + 1;
if(op == 1) update(l, r, x);
else if(op == 2) assign_val(l, r, x);
else if(op == 3) printf("%lld\n", ranking(l, r, x));
else printf("%lld\n", sum(l, r, x, y));
}
return 0;
}